package com.LeeCode;

/**
 * 监控二叉树
 */

public class Code968 {
    public static void main(String[] args) {
        Integer[] arr = {0, 0, null, 0};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code968().minCameraCover(root));
    }

    private int cameras = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 2) { // 根节点未被覆盖，则必须加一个摄像头
            cameras++;
        }
        return cameras;
    }

    /**
     * 返回值含义：
     * 0: 已覆盖
     * 1: 有摄像头
     * 2: 未被覆盖
     */
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0; // 空节点认为已被覆盖
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        // 如果左或右未被覆盖，则当前节点必须放摄像头
        if (left == 2 || right == 2) {
            cameras++;
            return 1; // 当前节点安装摄像头
        }

        // 如果左或右有一个摄像头，当前节点已被覆盖
        if (left == 1 || right == 1) {
            return 0; // 已被覆盖
        }

        // 剩下的情况：左右都被覆盖，当前节点未被覆盖
        return 2;
    }
}
